package cn.bellychang.leetcode.question069;

/**
 * @author ChangLiang
 * @date 2021/3/8
 */
public class Solution {

    public int mySqrt(int x) {

        if(x<=1){
            return x;
        }

        int begin = 0;
        int end = x;
        while(begin < end){
            int mid = ((end - begin)>>1) + begin;
            if(mid == x / mid){
                return mid;
            }else if ( mid > x / mid){
                end = mid - 1;
            }else{
                begin = mid + 1;
            }
        }
        if(end <= x/end){
            return end;
        }
        return end - 1;
    }
}
